package solution;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-01-23
 * Time: 9:37
 */

//https://leetcode.cn/problems/sort-list/submissions/396927302/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
////节点数目较多，如若使用插入排序，时间复杂度较慢
////改用归并排序
//class Solution {
//    public ListNode sortList(ListNode head) {
//        return sortList(head, null);//多加一个null尾节点，方便后面的分操作
//    }
//
//    //分
//    public ListNode sortList(ListNode head, ListNode tail) {
//        if (head == null) {
//            return null;
//        }
//        if (head.next == tail) {
//            head.next = null;//由于与单链表不能和数组一样回退，所以左排了mid节点，右边就必须少一重复的个节点
//            return head;
//        }
//        ListNode slow = head;
//        ListNode fast = head;
//        while (fast != tail) {//找到中间节点（或者靠右侧的那个，因为要忽略右侧的那个）
//            slow = slow.next;
//            fast = fast.next;
//            if (fast != tail) {
//                fast = fast.next;
//            }
//        }
//        ListNode mid = slow;
//        ListNode list1 = sortList(head, mid);
//        ListNode list2 = sortList(mid, tail);//mid分别进入了分，对应上面的处理
//        ListNode sorted = merge(list1, list2);
//        return sorted;
//    }
//
//    //合
//    public ListNode merge(ListNode head1, ListNode head2) {
//        ListNode dummyHead = new ListNode(0);
//        ListNode temp = dummyHead;
//        ListNode temp1 = head1;
//        ListNode temp2 = head2;
//        while (temp1 != null && temp2 != null) {//同样对应上方置最后一个（链表尾）为null的操作
//            if (temp1.val <= temp2.val) {
//                temp.next = temp1;
//                temp1 = temp1.next;
//            } else {
//                temp.next = temp2;
//                temp2 = temp2.next;
//            }
//            temp = temp.next;
//        }
//        if (temp1 != null) {
//            temp.next = temp1;
//        } else if (temp2 != null) {
//            temp.next = temp2;
//        }
//        return dummyHead.next;
//    }
//}


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public ListNode sortList(ListNode head) {
//        if (head == null) {
//            return null;
//        }
//        int length = 0;
//        ListNode node  = head;
//        while (node != null) {
//            node = node.next;
//            length++;
//        }
//        ListNode dummyHead = new ListNode(0, head);
//        //设定head1和head2的长度，每次轮完整个链表后扩大2倍
//        for (int subLength = 1; subLength < length; subLength <<= 1) {
//            ListNode prev = dummyHead;
//            ListNode curr = dummyHead.next;
//            while (curr != null) {//直到链表尾才结束一轮
//                ListNode head1 = curr;
//                for (int i = 1; i < subLength && curr.next != null; i++) {//规定长度，以及不能超出链表尾
//                    curr = curr.next;
//                }//此时的curr为head1的尾或链表尾
//                ListNode head2 = curr.next;//第二条链表为head1的尾
//                curr.next = null;//head1结束的标志
//                curr = head2;
//                //开始找到head2的尾
//                for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {//排除链表已经结束的结果
//                    curr = curr.next;
//                }//此时的curr为head2的尾或链表尾
//                ListNode next = null;
//                if (curr != null) {//排除链表尾的情况
//                    next = curr.next;//记录剩余没排序的链表的位置
//                    curr.next = null;
//                }
//                ListNode merged = merge(head1, head2);
//                prev.next = merged;//将排好的拼接到hummyHead的后面
//                while (prev.next != null) {//将prev的位置置到结尾，为下一次拼接准备
//                    prev = prev.next;
//                }
//                curr = next;//将记录的没排的链表头赋值到循环的位置
//            }
//        }
//        return dummyHead.next;
//    }
//
//    public ListNode merge(ListNode head1, ListNode head2) {
//        ListNode dummyHead = new ListNode(0);
//        ListNode temp = dummyHead;
//        ListNode temp1 = head1;
//        ListNode temp2 = head2;
//        while (temp1 != null && temp2 != null) {
//            if (temp1.val <= temp2.val) {
//                temp.next = temp1;
//                temp1 = temp1.next;
//            } else {
//                temp.next = temp2;
//                temp2 = temp2.next;
//            }
//            temp = temp.next;
//        }
//        if (temp1 != null) {
//            temp.next = temp1;
//        } else if (temp2 != null) {
//            temp.next = temp2;
//        }
//        return dummyHead.next;
//    }
//}


